Szatnia

Limit pamięci: 128 MB

W Bajtocji odbywa się doroczny zlot bogatych mieszkańców. Zbierają się oni, by chwalić się swoimi zarobkami, butami Lebajtina i innymi luksusowymi rzeczami. Naturalnie, nie wszystkie rzeczy wnoszą na bankiet - płaszcze, kurtki czy parasole zostawiają w szatni, by odebrać je, wychodząc.

Na nieszczęście bogaczy szajka bajtockich złodziei planuje włamać się do szatni i ukraść część pozostawionych tam przedmiotów. Póki co szef szajki przegląda zaproponowane przez gangsterów plany skoku. Każdy plan wygląda następująco: złodzieje pojawiają się w szatni w chwili , zabierają przedmioty o wartości dokładnie i uciekają, przy czym cały skok zajmuje im czas . Szef gangu chciałby przede wszystkim wiedzieć, które z planów mają szansę się udać, a które nie. Plan ma szansę się udać, jeśli w chwili da się uzbierać przedmioty o łącznej wartości dokładnie , w taki sposób, żeby do momentu włącznie nikt nie przyszedł po żaden z kradzionych przedmiotów (w takim wypadku zawiadomiłby ochronę i ucieczka nie udałaby się). W szczególności, jeśli w chwili w ogóle nie da się dobrać przedmiotów o łącznej wartości , plan zostaje odrzucony. Znając moment przyniesienia i zabrania każdego przedmiotu, określ, które plany mają szansę powodzenia, a które skazane są na porażkę. Zakładamy, że jeśli przedmiot zostaje przyniesiony w momencie, w którym złodzieje mają dokonać skoku, mogą go już ukraść (patrz test przykładowy).

Wejście

W pierwszym wierszu standardowego wejścia znajduje się liczba całkowita (), reprezentująca liczbę przedmiotów, które zostaną pozostawione w szatni. W kolejnych wierszach znajdują się opisy przedmiotów. Każdy z nich składa się z trzech liczb całkowitych , i (, ), pooddzielanych pojedynczymi odstępami, oznaczających kolejno: wartość przedmiotu, moment, w którym zostanie przyniesiony do szatni, oraz moment, w którym zostanie z niej zabrany.

Następny wiersz zawiera liczbę () - liczbę planów przedstawionych przez szajkę. Każdy z nich jest opisany w jednym wierszu przez trzy liczby całkowite , i (, , ), pooddzielane pojedynczymi odstępami, oznaczające kolejno: moment, w którym złodzieje weszliby do szatni, wartość, jaką chcą uzyskać, oraz czas, jaki zajmie im kradzież.

W testach wartych 16% punktów zachodzi dodatkowy warunek .

W innych testach, również wartych 16% punktów, wszystkie przedmioty mają równe .

W jeszcze innych testach, wartych 24% punktów, wszystkie zapytania mają równe .

Wyjście

Dla każdego planu szajki określ, czy plan da się zrealizować, tj. ukraść przedmioty o wartości dokładnie i uciec, zanim ktoś upomni się o swoją rzecz. Jeśli plan jest wykonalny, Twój program powinien wypisać na standardowe wyjście słowo TAK, a w przeciwnym wypadku słowo NIE.

Przykład

Dla danych wejściowych:

5
6 2 7
5 4 9
1 2 4
2 5 8
1 3 9
5
2 7 1
2 7 2
3 2 0
5 7 2
4 1 5

poprawną odpowiedzią jest:

TAK
NIE
TAK
TAK
NIE

Autor zadania: Jan Kanty Milczek.